package leetcode.search;

/**
 有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。

 省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。

 给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，
 而 isConnected[i][j] = 0 表示二者不直接相连。

 返回矩阵中 省份 的数量。

 */
public class FindCircleNum547 {

    public int findCircleNum(int[][] isConnected) {
        int m = isConnected.length;

        if(m==0) return 0;
        int count=0;
        boolean []visit = new boolean[m];
        for (int i = 0; i < m; i++) {
            if(!visit[i]){//i所在的节点算一个
                dfs(isConnected,i,visit);//把i所在的节点标记
                count++;
            }
        }
        return  count;
    }

    //从第i个节点开始搜索
    private  void  dfs(int[][]grid,int i,boolean []visit){
        visit[i] = true;
        for (int j = 0; j < grid.length; j++) {
            if(grid[i][j]==1 && !visit[j]){
                dfs(grid,j,visit);
            }
        }
    }
}